In 1978 the distinguished mathematician Robert McEliece invented a Public Key Encryption system [1] based upon encoding information as codewords using an error correcting code from the family of Goppa [2] codes. A randomly chosen error pattern containing up to t bits is added to each codeword and several such constructed codewords make up the cryptogram. On reception the associated private key is used to invoke an error correcting decoder based upon the underlying Goppa code to correct the errored bits in each codeword, prior to retrieval of all of the message bits.
In U.S. Pat. No. 5,054,066, Riek and McFarland improved the security of the system by complementing the error patterns so as to increase the number of errors contained in the cryptogram [3] and cited other variations of the original system.
In the originally proposed Public Key encryption system [1] a codeword is generated from message bits by using a permuted, scrambled generator matrix of a Goppa code [2] of length n symbols, capable of correcting t errors. This matrix is the public key. The digital cryptogram is formed from codewords corrupted by exactly t randomly, or t pseudo-randomly, chosen bit errors. The security strength of the McEliece Public Key encryption system stems from the fact that a truly random binary error pattern is added to the encoded message as part of the digital cryptogram. The security is provided by the fact that it is impossible to remove the unknown bit errors unless the original unpermuted Goppa code, the private key, is known in which case the errors can be removed by correcting them and then descrambling the information bits in the codeword to recover the original message. Even with the same message and the same public key a different digital cryptogram is produced each time. The messages are encoded with a scrambled, binary mapped, permuted, version of a GF(2m) Goppa code. Without the knowledge of the particular Goppa code that is used, the error patterns cannot be corrected and the messages cannot be recovered. It is not possible to deduce which particular Goppa code is being used from the public key, which is the matrix used for encoding, because this matrix is a scrambled, permuted version of the original encoding matrix of the Goppa code, plus the fact that for a given in there are an extremely large number of Goppa codes [1]. In the original example given in [1], the codeword length n is 1024 and t is 50. The number of possible error combinations is 3.19×1085 equivalent to a secret key of length 284 bits.